class Solution
{
public:
    // 以每一个柱作为高，用两个单调栈向两侧找最远的底
    int largestRectangleArea(vector<int> &heights)
    {
        stack<int> st;
        int n = heights.size();
        vector<int> leftBound(n, -1), rightBound(n, n);
        for (int i = 0; i < n; ++i)
        {
            while (!st.empty())
            {
                if (heights[st.top()] >= heights[i])
                {
                    st.pop();
                }
                else
                {
                    break;
                }
            }
            if (!st.empty())
            {
                leftBound[i] = st.top();
            }
            st.push(i);
        }

        st = stack<int>();
        for (int i = n - 1; i >= 0; --i)
        {
            while (!st.empty())
            {
                if (heights[st.top()] >= heights[i])
                {
                    st.pop();
                }
                else
                {
                    break;
                }
            }
            if (!st.empty())
            {
                rightBound[i] = st.top();
            }
            st.push(i);
        }

        int maxArea = 0;
        for (int i = 0; i < n; ++i)
        {
            int area = heights[i] * (rightBound[i] - leftBound[i] - 1);
            maxArea = max(maxArea, area);
        }
        return maxArea;
    }

    // 以每一个柱作为最右侧，用单调栈找到左侧可能较大的高
    // 最坏情况下，heights单调递增，复杂度n^2，超时
    int singleDirectionTraverse(vector<int> &heights)
    {
        vector<int> increaseStack;
        int n = heights.size();
        int maxArea = 0;
        for (int i = 0; i < n; ++i)
        {
            while (!increaseStack.empty())
            {
                if (heights[increaseStack.back()] >= heights[i])
                {
                    increaseStack.pop_back();
                }
                else
                {
                    break;
                }
            }
            increaseStack.push_back(i);
            int area = (i + 1) * heights[increaseStack[0]];
            maxArea = max(maxArea, area);
            for (int j = 1; j < increaseStack.size(); ++j)
            {
                area = (i - increaseStack[j - 1]) * heights[increaseStack[j]];
                maxArea = max(maxArea, area);
            }
        }
        return maxArea;
    }
};